package likou.bingchaji;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/16 19:47
 */
//684. 冗余连接
public class _684_keyi {
    static class BCJ {
        BCJ bcj;

        BCJ() {
            this.bcj = this;
        }

        BCJ find() {
            if (bcj.bcj != bcj) {
                bcj = bcj.find();
            }
            return bcj;
        }

        void union(BCJ bcj) {
            this.find().bcj = bcj;
        }
    }

    private static int[] result = new int[2];//合并两个连通分量时，赋值答案

    public static int[] findRedundantConnection(int[][] edges) {
        BCJ[] unions = new BCJ[1001];
        for (int[] edge : edges) {
            int index1 = edge[0],index2 = edge[1];
            BCJ bcj1 = unions[index1],bcj2 = unions[index2];
            if (bcj1==null&&bcj2==null){
                BCJ b = new BCJ();
                unions[index1] = b;
                unions[index2] = b;
            }else if (bcj1==null){
                bcj1 = new BCJ();
                bcj1.union(bcj2);//绑定bcj2
                unions[index1] = bcj2;
            }else if (bcj2==null){
                bcj2 = new BCJ();
                bcj2.union(bcj1);
                unions[index2] = bcj2;
            }else {
                //find的目的是为了得到最终的终极绑定头头
                if (bcj1.find() != bcj2.find()){
                    result = edge;
                }else {
                    bcj1.union(bcj2);
                }
            }

        }
        return result;
    }
}
